﻿#include "RouterMeshless.h"
#include <algorithm>
#include <utility>
#include "../src_basics/utils.h"


using namespace std;

void RouterMeshless::run() {
	if (m_netTrees == nullptr) {
		cerr << "Error: RouterMeshless::run() m_netTrees == nullptr" << endl;
		return;
	}
	if (!m_priorityRule) {
		m_priorityRule = defaultPriorityRule;
	}
	// 对每个网络进行布线
	for (const auto& [netName, steinerTree] : *m_netTrees) {
		if (!steinerTree) continue;
		// 1.将steinerTree拆解成多组起点终点，并设置默认优先级规则
		vector<pair<PinPolygon*, PinPolygon*>> pinPairs = extractPinPairs(steinerTree);
		sort(pinPairs.begin(), pinPairs.end(), m_priorityRule);
		// 2.对单一网进行寻路，处理每个起点终点对
		std::vector<PathNode*> oneNetPath;
		for (const auto& pair : pinPairs) {
			for (auto& node : m_temp) {
				delete node;
			}
			m_temp.clear();
			PathNode* node_start = new PathNode(pair.first->m_center, pair.first);
			PathNode* node_end = new PathNode(pair.second->m_center, pair.second);
			node_start->insertAfter(node_end);
			oneNetPath.emplace_back(node_start);
			const Line line(node_start->position, node_end->position);
			// （1）获取穿过哪些cells
			vector<GridCell*> cells;
			m_gridManager->getCellsAlongLine(line, cells);

			// （2）搜索cells中的障碍物（可能穿过），合并，去重并按中心距排序，存入obss中
			unordered_set<PinPolygon*> obss;
			getCandidatePolygons(node_start, node_end, cells, obss);

			// （3）获取穿过的节点，并对节点进行排序
			vector<PathNode*> crossingNodesSorted;
			bool moreThanTwoNodes = getSortedNodes(line, obss, crossingNodesSorted);
			if (!moreThanTwoNodes)
				continue;

			// （4）依次Hug这些障碍物
			lineHugPolygons(node_start, node_end, crossingNodesSorted);

			// （5）推挤这些线段
			slideNodeLines(node_start, node_end);



			//// （3）获取真实相交的障碍物，并按照最近交点排序
			//vector<PathNode*> minMaxNodes;
			//getSortedObss(line, obss, minMaxNodes);

			 //（3）Hug障碍物
			//lineHugPolygon(obss, node_start, node_end);

			// （4）线段推移动，并插入到网格中

			// 释放m_temp内存
			
		}
		m_pathNodes[netName] = oneNetPath;
		// 4.对路径解重叠，并更新网格
		// 5.对路径解交叉，并更新网格


	}
}

void RouterMeshless::initializeGrid(double& gridSize) {
	if (m_bound.size() < 4) {
		cerr << "Error: Invalid boundary data. Expected 4 values: {minX, minY, maxX, maxY}" << endl;
		return;
	}
	// 检查nets是否为空
	if (!m_netTrees || m_netTrees->empty()) {
		cout << "Warning: No net trees to process" << endl;
		return;
	}
	double minX = m_bound[0];
	double minY = m_bound[1];
	double maxX = m_bound[2];
	double maxY = m_bound[3];
	if (minX >= maxX || minY >= maxY) {
		cerr << "Error: Invalid boundary range in initializeGrid" << endl;
		return;
	}
	// 创建网格管理器
	m_gridManager = std::make_unique<GridManager>(minX, minY, maxX, maxY, gridSize);

	// 将所有net中的多边形添加到网格中
	int totalPolygons = 0;
	for (const auto& [netName, steinerTree] : *m_netTrees) {
		if (!steinerTree)
			continue;

		// 使用lambda函数遍历斯坦纳树
		function<void(shared_ptr<SteinerNode>)> traverseTree = [&](shared_ptr<SteinerNode> node) {
			if (!node || !node->pin)
				return;
			m_gridManager->addPolygon(node->pin);// 将多边形添加到网格
			totalPolygons++;
			for (auto& child : node->children) // 递归遍历子节点
				traverseTree(child);
			};
		traverseTree(steinerTree);
	}
	// 将obss中的多边形添加到网格中
	for (auto& poly : *m_obss) {
		m_gridManager->addPolygon(&poly);
	}

	// 输出网格统计信息（用于调试）
	//if (m_gridManager) {
	//	auto& allCells = m_gridManager->getAllCells();
	//	int nonEmptyCells = 0;
	//	int maxPolygonsInCell = 0;
	//	for (auto& cell : allCells) {
	//		int polyCount = cell->getPolygons().size();
	//		if (polyCount > 0) {
	//			nonEmptyCells++;
	//			maxPolygonsInCell = max(maxPolygonsInCell, polyCount);
	//		}
	//	}
	//	cout << "================Grid statistics================" << endl;
	//	cout << "\tnon-empty cells: " << nonEmptyCells << endl;
	//	cout << "\tempty cells: " << allCells.size() - nonEmptyCells << endl;
	//	cout << "\tmax polygons in cell: " << maxPolygonsInCell << endl;
	//	cout << "================Grid statistics================" << endl;
	//}
}
// 从斯坦纳树中提取起点终点对
vector<pair<PinPolygon*, PinPolygon*>> RouterMeshless::extractPinPairs(shared_ptr<SteinerNode> steinerTree) {

	vector<pair<PinPolygon*, PinPolygon*>> pairs;
	if (!steinerTree) return pairs;
	// 使用BFS遍历斯坦纳树，收集所有连接关系
	queue<shared_ptr<SteinerNode>> q;
	unordered_set<shared_ptr<SteinerNode>> visited;

	q.push(steinerTree);
	visited.insert(steinerTree);

	while (!q.empty()) {
		auto currentNode = q.front();
		q.pop();

		// 处理当前节点的所有子节点
		for (auto& child : currentNode->children) {
			if (visited.find(child) == visited.end()) {
				visited.insert(child);
				q.push(child);

				// 添加起点终点对
				if (currentNode->pin && child->pin) {
					pairs.emplace_back(currentNode->pin, child->pin);
				}
			}
		}

		// 处理父节点（如果是双向连接）
		if (auto parent = currentNode->parent.lock()) {
			if (visited.find(parent) == visited.end()) {
				visited.insert(parent);
				q.push(parent);

				if (currentNode->pin && parent->pin) {
					pairs.emplace_back(currentNode->pin, parent->pin);
				}
			}
		}
	}

	return pairs;
}
void RouterMeshless::getCandidatePolygons
(
	const PathNode* node_start,			// input
	const PathNode* node_end,			// input
	const vector<GridCell*>& cells,		// input
	unordered_set<PinPolygon*>& obss	// output
) const {
	// 获取这些cells中的所有多边形，对于水平先和竖直线，用外包盒过滤无交点的多边形
	Line line(node_start->position, node_end->position);
	for (auto cell : cells) {
		for (PinPolygon* poly : cell->getPolygons()) {
			if (poly == node_start->pin || poly == node_end->pin) continue;
			if (obss.find(poly) == obss.end()) {
				if (abs(line.Pt1.x - line.Pt2.x) < CountMinValue) {
					//竖直线，用外包盒过滤，去掉左右两侧的多边形
					if (poly->m_box[0] > line.Pt1.x || poly->m_box[2] < line.Pt1.x)
						continue;
				}
				else if (abs(line.Pt1.y - line.Pt2.y) < CountMinValue) {
					//水平线，用外包盒过滤，去掉上下两侧的多边形
					if (poly->m_box[1] > line.Pt1.y || poly->m_box[3] < line.Pt1.y)
						continue;
				}
				obss.insert(poly);
			}
		}
	}
}

bool RouterMeshless::getSortedNodes(const Line& line, unordered_set<PinPolygon*>& obss, vector<PathNode*>& crossingNodes) {
	// 获取所有相交节点
	for (const auto& poly : obss) {
		getLinePolygonIntersections(line, poly, crossingNodes);
	}
	if (crossingNodes.size() < 2) {
		return false;
	}
	if (crossingNodes.size() % 2 != 0) {
		cout << "crossingNodes.size:" << crossingNodes.size() << endl;
		return false;
	}
	// 排序
	multimap<double, PathNode*> crossingNodesSorted;
	if (abs(line.Pt1.x - line.Pt2.x) > abs(line.Pt1.y - line.Pt2.y)) {
		for (PathNode* cur : crossingNodes) {
			double delta_x = abs(cur->position.x - line.Pt1.x);
			crossingNodesSorted.insert(make_pair(delta_x, cur));
		}
	}
	else {
		for (PathNode* cur : crossingNodes) {
			double delta_y = abs(cur->position.y - line.Pt1.y);
			crossingNodesSorted.insert(make_pair(delta_y, cur));
		}
	}
	crossingNodes.clear();
	for (auto& pair : crossingNodesSorted) {
		crossingNodes.emplace_back(pair.second);
	}
	return true;
}
bool RouterMeshless::getLinePolygonIntersections(const Line& line, PinPolygon* poly, vector<PathNode*>& crossingNodes) {
	if (!poly) return false;
	if (poly->m_edges.empty()) return false;
	PathNode* nodeAroundObs = new PathNode(poly->m_edges[0].Pt1);
	// 检查与多边形每条边的交点
	PathNode* cur = nodeAroundObs;
	PathNode* new_cur;
	int crossingPtNums = 0;
	for (Line& edge : poly->m_edges) {
		Point line_vec = line.getVector() / line.getLength();
		Point vec = edge.getVector() / edge.getLength();
		Point intersection;
		if (abs(cross(line_vec, vec)) > AngleMaxValue) {	// 不平行
			intersection = line.getCrossingPoint(edge);
			bool xInLineMid = intersection.x > min(line.Pt1.x, line.Pt2.x) && intersection.x < max(line.Pt1.x, line.Pt2.x);
			bool yInLineMid = intersection.y > min(line.Pt1.y, line.Pt2.y) && intersection.y < max(line.Pt1.y, line.Pt2.y);
			bool xInEdgeMid = intersection.x > min(edge.Pt1.x, edge.Pt2.x) && intersection.x < max(edge.Pt1.x, edge.Pt2.x);
			bool yInEdgeMid = intersection.y > min(edge.Pt1.y, edge.Pt2.y) && intersection.y < max(edge.Pt1.y, edge.Pt2.y);
			if ((xInLineMid || yInLineMid) && (xInEdgeMid || yInEdgeMid)) {	//交点在两条线段之间
				new_cur = new PathNode(intersection);
				crossingNodes.emplace_back(new_cur);
				crossingPtNums++;
				cur->insertAfter(new_cur);
				cur = new_cur;
			}
		}
		new_cur = new PathNode(edge.Pt2);
		cur->insertAfter(new_cur);
		cur = new_cur;
	}
	if (crossingPtNums < 2 || crossingPtNums % 2 != 0) {
		crossingNodes.resize(crossingNodes.size() - crossingPtNums);
		nodeAroundObs->deleteRelatedNodes();
		return false;
	}
	// 连接成环
	nodeAroundObs->prev = cur->prev;
	nodeAroundObs->prev->next = nodeAroundObs;
	delete cur;
	m_temp.emplace_back(nodeAroundObs);
	return true;
}

void RouterMeshless::lineHugPolygons(PathNode* node_start, PathNode* node_end, vector<PathNode*>& crossingNodes) {
	PathNode* start = node_start;
	size_t len_1 = crossingNodes.size() - 1;
	for (size_t i = 0; i < len_1; i += 2) {
		changeTwoNodesConnection(start, node_end, crossingNodes[i], crossingNodes[i + 1]);
		start = node_end->prev;
	}
}
bool RouterMeshless::changeTwoNodesConnection(PathNode* start, PathNode* end, PathNode* n1, PathNode* n2) {
	//1.计算两侧路径长度
	PathNode* cur = n1;
	double length1 = 0.0;
	while (cur != n2) {
		length1 += cur->position.distanceTo(cur->prev->position);
		cur = cur->prev;
		if (cur == n1)
			return false;
	}
	cur = n1;
	double length2 = 0.0;
	while (cur != n2) {
		length2 += cur->position.distanceTo(cur->next->position);
		cur = cur->next;
	}

	//2.选择最短路径，更新连接关系
	start->insertAfter(new PathNode(n1->position));
	start = start->next;
	if (length1 < length2) {
		PathNode* cur = n1;
		while (cur != n2) {
			cur = cur->prev;
			start->insertAfter(new PathNode(cur->position));
			start = start->next;
		}
	}
	else {
		PathNode* cur = n1;
		while (cur != n2) {
			cur = cur->next;
			start->insertAfter(new PathNode(cur->position));
			start = start->next;
		}
	}
	return true;
}

void RouterMeshless::slideNodeLines(PathNode* node_start, PathNode* node_end) {
	//1.定义算法的输入数据
	vector<Line> polyLines_input;
	Line line_input;
	Point offset_input;
	PathNode* cur = node_start;
	while (cur->next) {
		polyLines_input.emplace_back(cur->position, cur->next->position);
		cur = cur->next;
	}
	//3.设置算法输入数据
	
	//4.创建推挤对象,设置基本参数
	SlideLine slide;
	slide.setMode(0);
	slide.setInGreed(false);
	bool postOn = false;
	//5.执行算法
	int result = slide.pushSingleLine(polyLines_input, line_input, offset_input, postOn);
	//6.更新node
	//未完成
	/*while (cur->next != node_end) {

	}*/
	
}
/*
bool RouterMeshless::getSortedObss(const Line& line, std::vector<PinPolygon*>& obss, std::vector<PathNode*>& minMaxNodes) {	// i,i,io
	vector<pair<double, double>> crossingNodess;
	minMaxNodes.clear();
	for (auto& poly : obss) {
		vector<PathNode*> crossingNodes_oneObs;
		if (!getLinePolygonIntersections(line, poly, crossingNodes_oneObs))
			continue;
		PathNode* minNode = nullptr;
		PathNode* maxNode = nullptr;
		auto [minDist, maxDist] = setMinMaxNode(line, crossingNodes_oneObs, minNode, maxNode);
		crossingNodess.emplace_back(make_pair(minDist, maxDist));
		minMaxNodes.emplace_back(minNode);
		minMaxNodes.emplace_back(maxNode);
	}

	for (int i = 0; i < crossingNodess.size(); i++) {
		auto& pair = crossingNodess[i];
		obss.emplace_back(pair.second);
	}
	return true;
}
pair<double, double> RouterMeshless::setMinMaxNode(const Line& line, std::vector<PathNode*>& crossingNodes, PathNode* minNode, PathNode* maxNode) {
	//1.确定最近，最远点
	minNode = crossingNodes[0];		//最近点
	maxNode = minNode;					//最远点
	if (abs(line.Pt1.x - line.Pt2.x) > CountMinValue) {
		for (PathNode* cur : crossingNodes) {
			double delta_x = abs(cur->position.x - line.Pt1.x);
			if (delta_x < abs(minNode->position.x - line.Pt1.x))
				minNode = cur;
			if (delta_x > abs(maxNode->position.x - line.Pt1.x))
				maxNode = cur;
		}
		return { minNode->position.x - line.Pt1.x, maxNode->position.x - line.Pt1.x };
	}
	else {
		for (PathNode* cur : crossingNodes) {
			double delta_y = abs(cur->position.y - line.Pt1.y);
			if (delta_y < abs(minNode->position.y - line.Pt1.y))
				minNode = cur;
			if (delta_y > abs(maxNode->position.y - line.Pt1.y))
				maxNode = cur;
		}
		return { minNode->position.y - line.Pt1.y, maxNode->position.y - line.Pt1.y };
	}
}


// 查找线段经过的障碍物
void RouterMeshless::lineHugPolygon(const vector<PinPolygon*>& obss, PathNode* node_start, PathNode* node_end) {
	if (!node_start || !node_end || obss.empty()) return;
	PathNode* currentStart = node_start;
	PathNode* currentEnd = node_end;
	// 对每个障碍物进行处理
	for (auto obstacle : obss) {
		if (!processSingleObstacle(currentStart, currentEnd, obstacle)) {
			continue;
		}
		currentStart = node_end->prev;
	}
}


bool RouterMeshless::processSingleObstacle
(
	PathNode* start,
	PathNode* end,
	PinPolygon* obstacle
) {
	Line originalLine(start->position, end->position);

	// 获取线段与障碍物的交点
	vector<PathNode*> crossingNodes;
	if (!getLinePolygonIntersections(originalLine, obstacle, crossingNodes))
		return false;
	// Hug单个障碍物
	if (!changeNodesConnection(start, end, crossingNodes))
		return false;
	return true;
}

bool RouterMeshless::changeNodesConnection(PathNode* start, PathNode* end, std::vector<PathNode*>& crossingNodes) {
	//1.确定最近，最远点
	PathNode* n11 = crossingNodes[0];		//最近点
	PathNode* n21 = n11;					//最远点
	if (abs(start->position.x - end->position.x) > CountMinValue) {
		for (PathNode* cur : crossingNodes) {
			double delta_x = abs(cur->position.x - start->position.x);
			if (delta_x < abs(n11->position.x - start->position.x))
				n11 = cur;
			if (delta_x > abs(n21->position.x - start->position.x))
				n21 = cur;
		}
	}
	else {
		for (PathNode* cur : crossingNodes) {
			double delta_y = abs(cur->position.y - start->position.y);
			if (delta_y < abs(n11->position.y - start->position.y))
				n11 = cur;
			if (delta_y > abs(n21->position.y - start->position.y))
				n21 = cur;
		}
	}

	//2.将环拆分成2个链
	PathNode* n12 = new PathNode(n11->position);  //保留next
	n12->next = n11->next;
	n12->next->prev = n12;
	n11->next = nullptr;  // 保留prev

	PathNode* n22 = new PathNode(n21->position);
	n22->prev = n21->prev;
	n22->prev->next = n22;		// 保留next
	n21->prev = nullptr;

	//3.计算两侧路径长度
	PathNode* cur = n11;
	double length1 = 0.0;
	while (cur->prev) {
		length1 += cur->position.distanceTo(cur->prev->position);
		cur = cur->prev;
	}
	cur = n12;
	double length2 = 0.0;
	while (cur->next) {
		length2 += cur->position.distanceTo(cur->next->position);
		cur = cur->next;
	}

	//4.选择最短路径，更新连接关系
	if (length1 < length2) {
		PathNode* pre_cur = start;
		cur = n11;
		while (cur) {
			PathNode* temp = cur->prev;
			pre_cur->insertAfter(cur);
			pre_cur = cur;
			cur = temp;
		}
		n12->deleteRelatedNodes();
	}
	else {
		start->next = n12;
		n12->prev = start;
		end->prev = n22;
		n22->next = end;
		n11->deleteRelatedNodes();
	}
	return true;
}


*/



